package com.lfg.leetcode.leetcode300;


public class No330minPatches {
    public static void main(String[] args) {
        System.out.println(minPatches(new int[]{1, 2, 31, 33}, 2147483647));
    }

    public static int minPatches(int[] nums, int n) {
        int cnt = 0;
        long right = 1;
        int index = 0;
        while (right <= n) {
            if (index < nums.length && right >= nums[index]) {
                right += nums[index++];
            } else {
                right = right << 1;
                cnt++;
            }
        }
        return cnt;
    }

}



